#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/03/06
# @Author   :Changshu
# @File     :Exercise15.py
# 15. 三数之和


def threeSum(nums: list) -> list:
	res = []
	if len(nums) < 3:
		return res
	# 排序
	sorted_nums = sorted(nums)
	for i in range(0, len(sorted_nums)):
		if i != 0 and sorted_nums[i] == sorted_nums[i - 1]:
			continue
		k = len(sorted_nums) - 1
		for j in range(i + 1, len(sorted_nums)):
			if j != i + 1 and sorted_nums[j] == sorted_nums[j - 1]:
				continue
			while j < k and sorted_nums[i] + sorted_nums[j] + sorted_nums[k] > 0:
				k -= 1
			if j == k:
				break
			if sorted_nums[i] + sorted_nums[j] + sorted_nums[k] == 0:
				res.append([sorted_nums[i], sorted_nums[j], sorted_nums[k]])
	return res

if __name__ == '__main__':
	a=[-1,0,1,2,-1,-4]
	b=threeSum(a)
	print(b)